﻿// 0905train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <deque>


using namespace std;

/*
 A、B 两个人玩一个数字比大小的游戏。在游戏开始前，两人各自拿到一个长度相同的数字序列，两个序列中的数字互不相同且随机排列。

规则  
1. 每一轮，A 和 B 各自从自己的序列中挑选一个数字进行比较：  
   - 若 A 的数字大，A 得 1 分，B 扣 1 分；  
   - 若 B 的数字大，B 得 1 分，A 扣 1 分；  
   - 若相等，双方分数不变。  
2. 用过的数字立即丢弃，不得再用。  
3. 假设 A 事先知道 B 的整个序列，并且总是由 B 先选数字并明示给 A。  
4. 目标：计算 A 可能获得的最大分数。

输入描述  
第一行：一个整数 N，表示数字序列的长度。  
第二行：N 个整数，A 的数字序列。  
第三行：N 个整数，B 的数字序列。

输出描述  
输出一个整数，表示 A 可能赢 B 的最大分数。

备注  
采用贪心策略：能赢的一定要赢，不能赢的要尽量减少损失。

示例  
输入  
3  
4 8 10  
3 6 4  

输出  
3  

说明  
序列 A：4 8 10  
序列 B：3 6 4  
一种能达到最大分数 3 的对局顺序：  
1) A 选 4，B 选 3 → A 得 1 分  
2) A 选 8，B 选 6 → A 得 1 分  
3) A 选 10，B 选 4 → A 得 1 分  
最终 A 赢 3 分。
 */
class Solution01
{
public:
    Solution01(vector<int>&a_vec, vector<int>&b_vec)
    {
        sort(a_vec.begin(), a_vec.end());
        sort(b_vec.begin(), b_vec.end());

        //初始化4个指针
        int left_a = 0, right_a = a_vec.size() - 1;
        int left_b = 0, right_b = b_vec.size() - 1;

        int result = 0;
        while (left_a<=right_a)
        {
            //right_a>right_b right_a--;right_b--
            if (a_vec[right_a]>b_vec[right_b])
            {
                right_a--;
                right_b--;
                //最强a碰最强b，a胜
                result += 1;
            }
            else if (a_vec[right_a] < b_vec[right_b])
            {
                //left_a++;right_b--;
                //最弱a消耗最强b
                left_a++;
                right_b--;
                //a失败
                result -= 1;
            }
            else
            {
                if (a_vec[left_a]>b_vec[left_b])
                {
                    left_a++;
                    left_b++;
                    //最弱a碰最弱b，a胜
                    result += 1;
                }
                else
                {
                    //最弱a消耗最强b
                    left_a++;
                    right_b--;
                    //a失败
                    result -= 1;
                }

            }
            //while
        }

        cout << result;
	    //Solution01
    }
};


/*
 N个人围成一圈，按顺时针从1到N编号
编号为1的人从1开始喊数，下一个人喊的数字为上一个人的数字加1
数字是7的倍数 数字本身含有7的话
喊“过”
假定玩这个游戏的N个人都没有失误地在正确的时机喊了“过”
当喊到数字K时，可以统计每个人喊"过"的次数

现给定一个长度为N的数组，存储了打乱顺序的每个人喊"过"的次数
请把它还原成正确的顺序，即数组的第i个元素存储编号i的人喊“过”的次数

输入描述
输入为一行，为空格分隔的喊"过"的次数
注意K并不提供，K不超过200，而数字的个数即为N

输出描述
输出为一行，为顺序正确的喊"过"的次数，也由空格分隔

输入
0 1 0
输出
1 0 0

一共只有一次喊"过"，那只会发生在需要喊7时
按顺序，编号为1的人会遇到7，故输出1 0 0
注意，结束时的K不一定是7，也可以是8、9等，喊过的次数都是1 0 0
 */
class Solution02
{
public:
    bool isTarget(int num)
    {
        //数字是7的倍数 数字本身含有7的话
        if (num%7==0)
        {
            return true;
        }

        string num_str = to_string(num);
        for (auto&oh_char:num_str)
        {
            if (oh_char == '7')
                return true;
        }
        return false;
        //isTarget
    }

    Solution02(vector<int>&origin_vec)
    {
        vector<int>sort_origin = origin_vec;
        sort(sort_origin.begin(), sort_origin.end());
	    //模拟完sort，两个sort数组相等，就是正确的序列
        int v_size = origin_vec.size();

        vector<int>exec_vec(v_size);

        int curr = 1;
        int index = 0;
        
        while (true)
        {
            //N个人围成一圈
            //从1开始喊数
            if (isTarget(curr))
            {
                exec_vec[index] += 1;
                vector<int>sort_exec = exec_vec;
                sort(sort_exec.begin(), sort_exec.end());

                if (sort_exec==sort_origin)
                {
                    break;
                }

            }
            curr++;
            if (index==v_size-1)
            {
                index = 0;
            }
            else
            {
                index++;
            }

        }

        for (int i=0; i<v_size; i++)
        {
            cout << exec_vec[i];
            if (i!=v_size-1)
            {
                cout << ' ';
            }
        }

        //Solution02
    }
};


/*
 一农夫带着m只羊，n只狼过河，农夫有一条可载x只狼/羊的船
农夫在时或者羊的 数量大于狼时，狼不会攻击羊；农夫在不损失羊的情况下，运输几次可以完成运输？
只计算农夫去对岸的次数，回程时农夫不会运送羊和狼

输入描述
输入参数为m，n，x
m为羊的数量、n为狼的数量、x为可载狼和羊的数量

输出描述
返回运输次数即可
如果无法完成运输返回0

补充说明
农夫在或农夫离开后羊的数量大于狼的数量时，狼不会攻击羊。农夫不占用船的容量

输入
5 3 3
输出
3
第一次运2只狼
第二次运3只羊
第三次运2只羊和1只狼

一农夫带着m只羊，n只狼过河，农夫有一条可载x只狼/羊的船
5只羊 3只狼过河 可载3只狼
 */
class Solution03
{
public:
    string getStateStr(vector<int>&state_node)
    {
        string state_str;
        for (int i=0; i<state_node.size();i++)
        {
            state_str += to_string(state_node[i]);
	        if (i!=state_node.size()-1)
	        {
                state_str += ',';
	        }
        }
        return state_str;
	    //updateStateMap
    }
    void updateQueue(vector<int>top_node, deque<vector<int>>&bfs_queue, int limit)
    {
        
        for (int sheep_num=0; sheep_num<=min(limit, top_node[0]); sheep_num++)
        {
            for (int wolf_num = 0; wolf_num <= min(limit - sheep_num, top_node[1]);wolf_num++)
            {
                vector<int>update_node = {
                    top_node[0] - sheep_num, //本岸羊-运输羊
                    top_node[1] - wolf_num, //本岸狼-运输狼
					top_node[2] + sheep_num, //对岸羊
                    top_node[3] + wolf_num //对岸狼
                };

                if (update_node[0]==0 && update_node[1]==0)
                {
                    is_find = true;
                    return;
                }

                //判断update_vec是否合法
                //羊的数量大于狼时，狼不会攻击羊
                if (update_node[0] > 0 && update_node[0] <= update_node[1]) continue;
                if (update_node[2] > 0 && update_node[2] <= update_node[3]) continue;

                string update_state_str = getStateStr(update_node);
                //该状态已经搜索过了
                if (state_set.count(update_state_str) > 0) continue;

                bfs_queue.push_back(update_node);
                state_set.insert(update_state_str);
            }
        }


    }

    Solution03(int sheep_count, int wolf_count, int limit)
    {
        //初始化bfs
        //本岸羊，本岸狼，对岸羊，对岸狼
        //羊+狼最多消耗limit的情况下，什么时候消耗完
        vector<int>node = { sheep_count, wolf_count, 0, 0 };
        deque<vector<int>>bfs_queue;
        bfs_queue.push_back(node);

        string origin_state_str = getStateStr(node);
        state_set.insert(origin_state_str);

        int search_count = 0;
        while (!bfs_queue.empty())
        {
            int q_size = bfs_queue.size();
            search_count++;

            for (int i=0; i<q_size; i++)
            {
                vector<int>top_node = bfs_queue.front();
                bfs_queue.pop_front();
                
                updateQueue(top_node, bfs_queue, limit);
            }

            if (is_find) break;

            //while (!bfs_queue.empty())
        }

        if (!is_find)
        {
            cout << 0;
            return;
        }

        cout << search_count;
	    //Solution03
    }
private:
    bool is_find = false;
    unordered_set<string>state_set;
};

int main()
{
    {
        //5 3 3
        int sheep_count, wolf_count, limit;
        cin >> sheep_count >> wolf_count >> limit;
        //int sheep_count=5, wolf_count=3, limit=3;

        Solution03 solu(sheep_count, wolf_count, limit);

        return 0;
    }
	{
        vector<int>num_vec;
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (oh_sstream>>token)
        {
            num_vec.push_back(stoi(token));
        }

        Solution02 solu(num_vec);

        return 0;
	}
    int v_size;
    cin >> v_size;
    vector<int>a_vec(v_size);
    vector<int>b_vec(v_size);

    for (int i=0; i<v_size; i++)
    {
        cin >> a_vec[i];
    }

    for (int i = 0; i < v_size; i++)
    {
        cin >> b_vec[i];
    }
    Solution01 solu(a_vec, b_vec);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
